
import java.util.ArrayList;
import java.util.Iterator;
import java.util.List;
import java.util.Vector;
import java.util.Set;
import java.util.HashSet;

import java.io.PrintWriter;
import java.io.FileOutputStream;
import java.io.FileNotFoundException;

public class PlanningGraph {

	Vector <Set<Concept>> PLevels;
	Vector <Set<Service>> ALevels;
	Set <Concept> goalSet;
	Set <Concept> givenSet;
	
	public PlanningGraph() {
		PLevels = new Vector<Set<Concept>>();
		ALevels = new Vector<Set<Service>>();
		goalSet = new HashSet<Concept>();
		givenSet = new HashSet<Concept>();
	}
	
	public void addGivenConcept(Concept c) {
		givenSet.add(c);
	}
	
	public void addGoalConcept(Concept c) {
		goalSet.add(c);
	}
	
	public void GraphPlan(Set<Service> services) {
		int i = 0;
		long startTime = System.currentTimeMillis();
		long endTime;
		long totalTime;
		this.ALevels.addElement(null);
		PLevels.addElement(givenSet);
		boolean reachgoal = PLevels.elementAt(i).containsAll(goalSet);
		boolean reachend = FixedPoint(i);
		System.out.println("************ This forward planning graph is shown as follows**************");
		//Input concepts
		System.out.print("Input concepts: ");
		for (Concept c: givenSet)
			System.out.print(c.getName() + " ");
		System.out.println();
		//Goal concepts
		System.out.print("Goal concepts: ");
		for (Concept c: goalSet)
			System.out.print(c.getName() + " ");
		System.out.println();
		System.out.println();

		while(!reachgoal && !reachend) {
			ExpandGraph(services, i);
			i++;
			reachgoal = PLevels.elementAt(i).containsAll(goalSet);
			reachend = FixedPoint(i);
		}
		
		if(PLevels.elementAt(i).containsAll(goalSet)) {
			endTime   = System.currentTimeMillis();
			totalTime = endTime - startTime;
			System.out.println("========================================");
			System.out.println("Forward search time: " + totalTime + "ms");
			int invokedServices = 0;
			for (int j = 1; j < ALevels.size(); j++)
				invokedServices += ALevels.elementAt(j).size();
			System.out.println("Invoked services: " + invokedServices);
			System.out.println("Levels: " + (ALevels.size()-1));
			System.out.println("========================================");
			System.out.println();
			
			System.out.println("Check all concepts' indexes");

			System.out.println("************ This solution graph is shown as follows************** ");
			System.out.print("InputConcepts: ");
			Iterator<Concept> it = givenSet.iterator();
			while(it.hasNext()) {
				System.out.print(it.next().getName() + " ");
			}			
			System.out.println("");
			it = goalSet.iterator();
			System.out.print("OutputConcepts: ");
			while(it.hasNext()) {
				System.out.print(it.next().getName() + " ");
			}			
			System.out.println("");
			ExtractPlan(i);
		}
		else {
		}
		if(FixedPoint(i)) {
			System.out.println("****************Reached fixed point, no solution****************");
		}
	
	}
	
	private void  ExpandGraph(Set<Service> services, int i) {
		Iterator<Service> it = services.iterator();
		Set<Service> selectedServices = new HashSet<Service>();
		Set<Concept> newConcept = new HashSet<Concept>();
		//build up each p level(newConcept set) and a level(selectedServices set)
        while (it.hasNext()) {
        	Service service = (Service)it.next();
        	if(PLevels.elementAt(i).containsAll(service.getInputConcepts())) {
        		selectedServices.add(service);
        		newConcept.addAll(service.getOutputConcepts());
    			for(Concept c :service.getOutputConcepts()) {
    				c.setOutputServices(service);
    			}
        		
        	}
        }
        
        //add the newConcepts and selectedServices set into one layer of a level and p level
        ALevels.addElement(selectedServices);
        newConcept.addAll(PLevels.elementAt(i));
        PLevels.addElement(newConcept);
        services.removeAll(selectedServices);
        //print out this layer's information
        System.out.println("*****************" + "Level" + (i+1) + "*********************");
        System.out.print("Service: ");
		for(Service obj :ALevels.elementAt(i+1))
		{
			System.out.print(obj.getId() + " ");
		}
		System.out.println();
		System.out.println("Number of Services:" + ALevels.elementAt(i+1).size());
		System.out.println("Number of Concepts: " + PLevels.elementAt(i+1).size());
        System.out.println();
	}
	
	private void ExtractPlan(int i) {
		int layer = i;
		long startTime = System.currentTimeMillis();
		Set<Concept> subgoal = new HashSet<Concept>();
		
		//pick goal from p[i] as first subgoal
		for(Concept pc:PLevels.lastElement()) {
			for(Concept gc : goalSet) {
				if(pc.equals(gc)) {
					subgoal.add(pc);
				}
			}
		}
		
		Vector <Set<Service>> solutions = new Vector<Set<Service>> ();
		Iterator<Concept> it = subgoal.iterator();
//		Random rnum = new Random();
//		int selectedSN = 0;
		int totalServices = 0;
		
		//build one layer's solution
		while(!subgoal.isEmpty()) {
			Set<Service> selectedServices = new HashSet<Service>();
			SetHandler<Service> handler = new SetHandler<Service>();
	        //select the minimal hitting set
	        List<Set<Service>> sets = new ArrayList<Set<Service>>();
//	        while(it.hasNext()) {
//	        	Concept concept = it.next();
//	        	sets.add(concept.getOutputServices());
//	        }
	        
	        while(it.hasNext()) {
	        	Concept con = it.next();
	        	Set<Service> temp = new HashSet<Service>();
	        	for (Service s: con.getOutputServices()) {
	        		for (Service s1: ALevels.elementAt(i))
	        		if (s.equals(s1) && (!s1.equals(null))) {
	        			temp.add(s1);
	        		}
	        	}
	        	if (!temp.isEmpty())
	        		sets.add(temp);
	        }
	        selectedServices.addAll(handler.handle(sets));
	        /*while(it.hasNext()) {
	        	Concept concept = it.next();
	        	sets.add(concept.getOutputServices());
	        }
	        selectedServices.addAll(handler.handle(sets));*/
//			
//			while(it.hasNext()) {
//				Concept concept = it.next();
//				//Randomly select an output services				
//				selectedSN = rnum.nextInt(concept.getOutputServices().size()) + 1;
//				int j = 1;
//				for(Service obj :concept.getOutputServices())
//				{
//					if (j == selectedSN)
//						selectedServices.add(obj);						
//				    j = j + 1;
//				}						
//			}
			for(Service s :selectedServices) {	
					subgoal.removeAll(s.getOutputConcepts());
					subgoal.addAll(s.getInputConcepts());
				
			}
			
			subgoal.removeAll(givenSet);
			Set<Concept> temp = new HashSet<Concept>();
			temp.addAll(subgoal);
			for(Concept pc:PLevels.elementAt(i-1)) {
				for(Concept gc : temp) {
					if(pc.equals(gc)) {
						subgoal.remove(gc);
						subgoal.add(pc);
					}
				}
			}
			
			it = subgoal.iterator();
			solutions.addElement(selectedServices);
			totalServices += selectedServices.size();		
			i--;
		}
		
		
		long endTime   = System.currentTimeMillis();
		long totalTime = endTime - startTime;

		int k = 0;
		
		while(k<solutions.size()){
			System.out.println("*****************Level" + (k+1) + "*************************");
			System.out.print("Services: ");
			for(Service s :solutions.elementAt(k)) {
				System.out.print(s.getId() + " ");
			}
			//System.out.print(solutions.elementAt(k).getId());
			System.out.println();
			System.out.println("Number of services:" + solutions.elementAt(k).size());
			System.out.println();
			k++;

		}
		System.out.println("========================================");

		System.out.println("BackTracking Time: " + totalTime + "ms");
		System.out.println("Invoked Services:" + totalServices);
		System.out.println("Level: " + solutions.size());
		System.out.println("========================================");
		
		CreateResultFile(solutions);
	}
	
	private boolean FixedPoint(int i) {
		if(i >= 1) {
			if(PLevels.elementAt(i).containsAll(PLevels.elementAt(i-1)) && PLevels.elementAt(i-1).containsAll(PLevels.elementAt(i)) )
				return true;
		}
		return false;	
	}
	private void CreateResultFile(Vector <Set<Service>> solutions){
		
		PrintWriter pw = null;
		try {
			pw = new PrintWriter(new FileOutputStream("result.txt"));
			
		} catch(FileNotFoundException e) {
			System.out.println("Could not create a file to write to. "+ " Please check for problems such as directory permission" + " or no available memory.");	
			System.out.print("Program will terminate.");
			System.exit(0);			   		   
		}
		int k = 0;
		while(k< solutions.size()) {
			Iterator<Service> it = solutions.elementAt(k).iterator();
        	Service s = it.next();
        	pw.print(s.getId());
			while(it.hasNext()) {
	        	s = it.next();
	        	pw.print("," + s.getId());
	        }
			pw.println("");
			k++;
		}
		pw.close();		// Close the file

 	}

}
